package suanfa;
//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//如果数组中不存在目标值 target，返回 [-1, -1]。
//你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//示例 1：
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
//示例 2：
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1]
//示例 3：
//输入：nums = [], target = 0
//输出：[-1,-1]
public class searchRange {public int[] searchRange(int[] nums, int target) {
    int[] ret=new int[2];
    ret[0]=ret[1]=-1;
    //处理边界情况
    if(nums.length == 0) return ret;
    //1.二分查找左端点
    int left=0;
    int right=nums.length-1;//这个可以用两个数字来测试一下必须用这个求中点的方法
    while(left<right){
        int mid=left+(right-left)/2;
        if(nums[mid]<target) left=mid+1;
        else right=mid;
    }
    if(nums[left] != target) return ret;
    else ret[0]=right;
    //2.二分查找判断右端点
//    left=right;
    left=0;//可以不用从0开始，直接从target最左边的端点开始就行
    right=nums.length-1;
    while(left<right){
        int mid=left+(right-left+1)/2;//这个可以用两个数字来测试一下必须用这个求中点的方法
        if(nums[mid]<=target) left=mid;
        else right=mid-1;
    }
    ret[1]=right;
    return ret;
}
}
